#include <iostream>
using namespace std;

void printArr(int arr[],int len);
/*常见排序算法：
 *          1.直接插入排序（稳定）
 *          2.希尔排序（不稳定）
 *          3.冒泡排序（稳定）
 *          4.快速排序（不稳定）
 *          5.选择排序（不稳定）
 *          6.堆排序（稳定）
 *          7.归并排序（稳定）
 *          8.基数排序(稳定，不考代码)*/

//1.直接插入排序
/*算法思想：
 *       每次从未排序的序列中取出一个元素插入到已经排序的序列中；
 *       初始状态下，第一个元素构成已排序序列；
 *       在遍历已排序序列时，采用从后往前遍历，找到第一个比目标元素小的元素；
 *       将后面的已排序元素向后依次移动一个，然后将目标元素插到其后面；
 *       以此类推，直到不存在未排序的元素；*/
void insertSort(int arr[],int len){
    int i,j,key;//设置指针i记录待插入元素位置，j用于遍历已排序序列；key记录待插入元素值
    for(i = 1; i < len; i++){//待插入元素从第二个开始，因为第一个元素天然有序
        key = arr[i];//记录待插入值
        j = i-1;//从有序序列最后一个开始遍历
        while(j >= 0 && arr[j] > key){//找到插入位置
            /*这步比较巧妙*/
            arr[j+1] = arr[j];//找的过程中后移元素
            j--;
        }
        arr[j+1] = key;//插入到合适的位置
    }
}

//2.希尔排序
/*算法思想：
 *       希尔排序是一种改进的插入排序，又叫缩小增量排序；
 *       设置增量d，将原数组划分成为一个个的子表，对各个子表进行插入排序；
 *       然后不断缩小增量d，重复上一步过程，直到d缩小到1；*/
void shellSort(int arr[],int len){
    int i,j,d,key;
    for (d = len/2; d > 0; d /= 2) {
        //d的取值：从n/2开始，每次减半，直至为1
        for(i = d;i<len;i++){//从子序列的第二个元素开始插排
            /*其中，每个子序列的插入排序不是连续完成的，即下一个插入的不一定是当前序列的元素*/
            /*以下是插入排序的模板*/
            key = arr[i];
            j = i-d;
            while(j >= 0 && arr[j] > key){
                arr[j+d] = arr[j];
                j -= d;
            }
            arr[j+d] = key;
        }
    }
}

//3.冒泡排序
/*算法思想：
 *       形象的理解为每一轮遍历数组会将数组中的最小泡（最小的元素）上浮到最前面
 *       1.从数组的最后一个元素开始，依次比较相邻的两个元素。
 *       2.如果前面的元素大于后面的元素，则交换这两个元素的位置，使得较小的元素“冒泡”到后面。
 *       3.继续比较下一对相邻元素，重复上述步骤，直到遍历到第二个元素。
 *       4.重复执行上述步骤，每一轮遍历可以确定一个最小（或最大）的元素，直到所有元素都被排序。*/
void bubbleSort(int arr[],int len){
    int i,j,tmp,tag = 1;
    for(i = 0;i < len && tag;i++){
        tag = 0;
        for(j = len-1;j > i;j--){
            if (arr[j] < arr[j-1]){
                tmp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = tmp;
                tag = 1;
            }
        }
    }
}

//4.快速排序
/*算法思想：
 *       1.选择一个基准元素（pivot）。
 *       2.将待排序数组中小于等于基准元素的元素移动到基准元素的左侧，大于基准元素的元素移动到基准元素的右侧，这个过程称为分区操作（partition）。
 *       3.对基准元素左侧和右侧的子数组分别进行递归，即重复步骤1和步骤2，直到所有的子数组都只剩下一个元素，此时排序完成。*/
//划分数组
int partition(int arr[],int left,int right);
//快速排序
void quickSort(int arr[],int left,int right){
    if (left >= right) return ;//递归出口，不符合划分条件
    int pivot = partition(arr,left,right);//一分为二（左小右大）
    quickSort(arr,left,pivot-1);//继续划分左右两半
    quickSort(arr,pivot+1,right);
}
int partition(int arr[],int left,int right){
    int pivot = arr[left];//每次选定第一个元素为基准（最佳的是中位数）
    while(left < right){
        /*由于选的是第一个元素为基准，所以先从右边往左边移动*/
        while(left < right && pivot < arr[right]){
            //找到右边第一个需要移动的元素
            right --;
        }
        arr[left] = arr[right];//移动
        while(left < right && pivot > arr[left]){
            //找到第一个左边需要移动的元素
            left ++;
        }
        arr[right] = arr[left];//移动
    }
    //此时左右指针重合，中间空出来一个位置，填入基准元素
    arr[left] = pivot;
    //返回基准指针，用于划分数组
    return left;
}

/*快速排序复习（默写）*/
int part(int arr[],int low,int high);
void qs(int arr[],int n,int low,int high){
    int mid = part(arr,low,high);
    part(arr,low,mid-1);
    part(arr,mid+1,high);
}
int part(int arr[],int low,int high){
    int pivot = arr[low];
    while(low < high){
        while(arr[high] >= pivot){
            high--;
        }
        arr[low] = arr[high];

        while(arr[low] < pivot){
            low++;
        }
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
}


//5.选择排序
/*算法思想：
 *       每次选择一个最值依次顺序插入*/
void selectSort(int arr[],int len){
    int i,j,tmp;
    for(i = 0; i < len-1;i++){
        for(j = i+1;j<len;j++){
            if (arr[j] < arr[i]){
                //交换当前节点和目标节点
                tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;
            }
        }
    }
}

//6.堆排序
/*算法思想：
 *       1.根据数组序列建立大根堆；
 *       2.取出堆顶元素加入到已排序数组中，并将最后一个元素移到堆顶；
 *       3.调整保持大根堆的性质；
 *       4.重复23步骤直至堆中没有元素；
 *实现方式：每次交换堆顶和最后一个元素，同时减少下一次操作的序列长度，使得在原来的空间上将最大的元素到达正确的位置上*/
//维护某个为根的大根堆
void updateHeap(int arr[],int len,int i);
//堆排序
void heapSort(int arr[],int len){
    //1.建堆
    /*关键：一定是从下往上构建*/
    int i;
    for(i = len/2-1;i >= 0;i--){
        //从第一个非叶子节点开始调整出一个大根堆
        updateHeap(arr,len,i);
    }
    //2.排序
    /*思路：每次取出堆顶元素，然后调整找出新的堆顶元素*/
    for(i = len-1;i > 0;i--){
        //2.1 交换堆顶和堆底
        int tmp = arr[i];
        arr[i] = arr[0];
        arr[0] = tmp;
        //2.2 维持堆性质（找出下一个最大的元素）
        updateHeap(arr,i,0);
    }
}
void updateHeap(int arr[],int len,int i){
    int max = i;
    /*注意和二叉树的区分，这里是数组下标，从0开始*/
    int left = 2*i + 1;
    int right = 2*i + 2;
    //找到根左右中最大的节点并和根节点交换
    if(left < len && arr[left] > arr[max]){
        max = left;
    }
    if (right < len && arr[right] > arr[max]){
        max = right;
    }
    if(max != i){//说明需要调整
        int tmp = arr[i];
        arr[i] = arr[max];
        arr[max] = tmp;
        /*关键：（递归）向下维持被调整位置为根的堆的性质*/
        updateHeap(arr,len,max);
    }
}

//7.归并排序
/*算法思想：
 *       1.递归划分子序列；
 *       2.合并有序的子序列；
 *       3.其中，只有一个元素序列为有序的，也就是递归的出口；*/
// 归并函数，将两个有序数组合并为一个有序数组
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;
    // 创建临时数组
    int L[n1], R[n2];
    // 复制数据到临时数组 L[] 和 R[]
    for (i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    // 归并临时数组到 arr[]
    i = 0;  // 初始化第一个子数组的索引
    j = 0;  // 初始化第二个子数组的索引
    k = left;  // 初始合并子数组的索引
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // 复制 L[] 的剩余元素（如果有）到 arr[]
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // 复制 R[] 的剩余元素（如果有）到 arr[]
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
// 归并排序函数
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        // 分割数组
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        // 归并已分割的数组
        merge(arr, left, mid, right);
    }
}

void printArr(int arr[],int len){
    for (int i = 0; i < len; ++i) {
        printf("%d ",arr[i]);
    }
    printf("\n");
}
int main(){

    int arr1[]= {10,4,7,3,2,6,1,9,8,5};
    printArr(arr1,10);
//    shellSort(arr1,10);
//    insertSort(arr1,10);
//    shellSort(arr1,10);
//    bubbleSort(arr1,10);
//    quickSort(arr1,0,9);
//    selectSort(arr1,10);
    heapSort(arr1,10);
//    mergeSort(arr1,0,9);
    printArr(arr1,10);

    return 0;
}